package com.leetcode.partition5;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/9/7 10:53
 */
public class LC438找到字符串中所有字母异位词 {

    public static List<Integer> findAnagrams(String s, String p) {
        return slidingWindow(s, p);
    }

    public static void main(String[] args) {
        String s = "aaaaaaaaaa", p = "aaaaaaaaaaaaa";
        System.out.println(findAnagrams(s, p));
    }

    private static List<Integer> slidingWindow(String s, String p) {
        List<Integer> answersList = new ArrayList<>();
        if (s.length() < p.length()) return answersList;
        char[] target = p.toCharArray();
        char[] temp = s.substring(0, p.length()).toCharArray();
        int left = 0;

        int[] targetTable = new int[26];
        int[] tempTable = new int[26];
        //得到p串和temp串的哈希表
        for (char c : target) targetTable[c - 'a']++;
        for (char c : temp) tempTable[c - 'a']++;
        if (Arrays.equals(targetTable, tempTable)) {
            answersList.add(0);
        }

        for (int right = p.length(); right < s.length(); right++, left++) {
            tempTable[s.charAt(right) - 'a']++;
            tempTable[s.charAt(left) - 'a']--;
            if (Arrays.equals(tempTable, targetTable)) {
                answersList.add(left + 1);
            }
        }
        return answersList;
    }

    private static List<Integer> doublePointer(String s, String p) {
        List<Integer> answers = new ArrayList<>();
        char[] target = p.toCharArray();
        Arrays.sort(target);
        for (int left = 0, right = p.length(); right <= s.length(); left++, right++) {
            char[] temp = s.substring(left, right).toCharArray();
            Arrays.sort(temp);
            if (Arrays.equals(target, temp)) {
                answers.add(left);
            }
        }
        return answers;
    }
}
